package com.tianji.promotion.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 基于回溯算法的全排列工具类
 */
public class PermuteUtil {
    /**
     * 将[0~n)的所有数字重组，生成所有可能的排列组合（包括不同长度）
     *
     * @param n 数字n
     * @return 所有排列组合
     */
    public static List<List<Byte>> permute(int n) {
        List<List<Byte>> res = new ArrayList<>();
        List<Byte> input = new ArrayList<>(n);
        for (byte i = 0; i < n; i++) {
            input.add(i);
        }
        boolean[] used = new boolean[n];
        backtrack(new ArrayList<>(), input, used, res);
        return res;
    }

    /**
     * 将指定集合中的元素重组，生成所有可能的排列组合（包括不同长度）
     *
     * @param input 输入的集合
     * @param <T>   集合类型
     * @return 所有排列组合
     */
    public static <T> List<List<T>> permute(List<T> input) {
        List<List<T>> res = new ArrayList<>();
        boolean[] used = new boolean[input.size()];
        backtrack(new ArrayList<>(), input, used, res);
        return res;
    }

    private static <T> void backtrack(List<T> path, List<T> input, boolean[] used, List<List<T>> res) {
        // 只要当前路径非空，就添加到结果中
        if (!path.isEmpty()) {
            res.add(new ArrayList<>(path));
        }
        for (int i = 0; i < input.size(); i++) {
            if (used[i]) {
                continue;
            }
            // 选择当前元素
            used[i] = true;
            path.add(input.get(i));
            // 递归探索
            backtrack(path, input, used, res);
            // 撤销选择
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}